The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance the Tractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to the P‐Cognition thesis. (...) This article explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by the FPT‐Cognition thesis as an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

Many compelling examples have recently been provided in which people can achieve impressive epistemic success, e.g. draw highly accurate inferences, by using simple heuristics and very little information. This is possible by taking advantage of the features of the environment. The examples suggest an easy and appealing naturalization of rationality: on the one hand, people clearly can apply simple heuristics, and on the other hand, they intuitively ought do so when this brings them high accuracy at little cost.. The ‘ought-can’ (...) principle is satisfied, and rationality is meaningfully normative. We show, however, that this naturalization program is endangered by a computational wrinkle in the adaptation process taken to be responsible for this heuristics-based (‘ecological’) rationality: for the adaptation process to guarantee even minimal rationality, it requires astronomical computational resources, making the problem intractable. We consider various plausible auxiliary assumptions in attempt to remove this obstacle, and show that they do not succeed; intractability is a robust property of adaptation. We discuss the implications of our findings for the project of naturalizing rationality. (shrink)

Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...) of intractability is solved by recourse to ‘as if’ explanations critically depends, inter alia, on the semantics of the ‘as if’ connective. We examine the five most sensible explications in the literature, and conclude that none of them circumvents the problem. As a result, rational ‘as if’ explanations must obey the minimal computational constraint of tractability. (shrink)

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

People cannot understand intentions behind observed actions by direct simulation, because goal inference is highly context dependent. Context dependency is a major source of computational intractability in traditional information-processing models. An embodied embedded view of cognition may be able to overcome this problem, but then the problem needs recognition and explication within the context of the new, layered cognitive architecture.

Intractability is a growing concern across the cognitive sciences: while many models of cognition can describe and predict human behavior in the lab, it remains unclear how these models can scale to situations of real-world complexity. Cognition and Intractability is the first book to provide an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science. Covering both classical and parameterized complexity analysis, it introduces the mathematical concepts and proof techniques that can be used (...) to test one's intuition of tractability. It also describes how these tools can be applied to cognitive modeling to deal with intractability, and its ramifications, in a systematic way. Aimed at students and researchers in philosophy, cognitive neuroscience, psychology, artificial intelligence, and linguistics who want to build a firm understanding of intractability and its implications in their modeling work, it is an ideal resource for teaching or self-study. (shrink)

Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that (...) theory of mind reasoning, so formalized, indeed is intractable. Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind. (shrink)

Advancement in cognitive science depends, in part, on doing some occasional ‘theoretical housekeeping’. We highlight some conceptual confusions lurking in an important attempt at explaining the human capacity for rational or coherent thought: Thagard & Verbeurgt’s computational-level model of humans’ capacity for making reasonable and truth-conducive abductive inferences (1998; Thagard, 2000). Thagard & Verbeurgt’s model assumes that humans make such inferences by computing a coherence function (f_coh), which takes as input representation networks and their pair-wise constraints and gives as output (...) a partition into accepted (A) and rejected (R) elements that maximizes the weight of satisfied constraints. We argue that their proposal gives rise to at least three difficult problems. (shrink)

Four articles in this issue of topiCS (volume 4, issue 1) argue against a computational approach in cognitive science in favor of a dynamical approach. I concur that the computational approach faces some considerable explanatory challenges. Yet the dynamicists’ proposal that cognition is self-organized seems to only go so far in addressing these challenges. Take, for instance, the hypothesis that cognitive behavior emerges when brain and body (re-)configure to satisfy task and environmental constraints. It is known that for certain systems (...) of constraints, no procedure can exist (whether modular, local, centralized, or self-organized) that reliably finds the right configuration in a realistic amount of time. Hence, the dynamical approach still faces the challenge of explaining how self-organized constraint satisfaction can be achieved by human brains and bodies in real time. In this commentary, I propose a methodology that dynamicists can use to try to address this challenge. (shrink)

Single cell recordings in monkeys provide strong evidence for an important role of the motor system in action understanding. This evidence is backed up by data from studies of the (human) mirror neuron system using neuroimaging or TMS techniques, and behavioral experiments. Although the data acquired from single cell recordings are generally considered to be robust, several debates have shown that the interpretation of these data is far from straightforward. We will show that research based on single-cell recordings allows for (...) unlimited content attribution to mirror neurons. We will argue that a theoretical analysis of the mirroring process, combined with behavioral and brain studies, can provide the necessary limitations. A complexity analysis of the type of processing attributed to the mirror neuron system can help formulate restrictions on what mirroring is and what cognitive functions could, in principle, be explained by a mirror mechanism. We argue that processing at higher levels of abstraction needs assistance of non-mirroring processes to such an extent that subsuming the processes needed to infer goals from actions under the label ?mirroring? is not warranted. (shrink)

Bayesian models are often criticized for postulating computations that are computationally intractable (e.g., NP-hard) and therefore implausibly performed by our resource-bounded minds/brains. Our letter is motivated by the observation that Bayesian modelers have been claiming that they can counter this charge of “intractability” by proposing that Bayesian computations can be tractably approximated. We would like to make the cognitive science community aware of the problematic nature of such claims. We cite mathematical proofs from the computer science literature that show intractable (...) Bayesian computations, such as postulated in existing Bayesian models, cannot be tractably approximated. This does not mean that human brains do not (or cannot) implement the type of algorithms that Bayesian modelers are advancing, but it does mean that proposing that they do by itself does nothing to parry the charge of intractability, because the postulated algorithms are as intractable (i.e., require exponential time) as the computations they try to approximate. Besides our negative message for the community, our letter also makes a positive contribution by referring to a methodology that Bayesian modelers can use to try and parry the charge of intractability in a mathematically sound way. (shrink)

Barbey & Sloman (B&S) advocate a dual-process (two-system) approach by comparing it with an alternative perspective (ecological rationality), claiming that the latter is unwarranted. Rejecting this alternative approach cannot serve as sufficient evidence for the viability of the former.

Leech et al. present a connectionist algorithm as a model of (the development) of analogizing, but they do not specify the algorithm's associated computational-level theory, nor its computational complexity. We argue that doing so may be essential for connectionist cognitive models to have full explanatory power and transparency, as well as for assessing their scalability to real-world input domains.

Paul ThagardCambridge, MA: MIT press, 2006313 pages, ISBN: 026220164X (hbk); $36.00Can human beliefs and inferences be understood as a form of coherence maximization? This question underlies much o...

This paper focuses on the cognitive/computational and evolutionary levels. It describes three proposals to make cognition computationally tractable, namely: Resource Rationality, the Adaptive Toolbox and Massive Modularity. While each of these proposals appeals to evolutionary considerations to dissolve the intractability of cognition, Rich, Blokpoel, de Haan, and van Rooij argue that, in each case, the intractability challenge is not resolved, but just relocated to the level of evolution.

This paper focuses on the cognitive/computational and evolutionary levels. It describes three proposals to make cognition computationally tractable, namely: Resource Rationality, the Adaptive Toolbox and Massive Modularity. While each of these proposals appeals to evolutionary considerations to dissolve the intractability of cognition, Rich, Blokpoel, de Haan, and van Rooij argue that, in each case, the intractability challenge is not resolved, but just relocated to the level of evolution.

Cimpian et al. observed that we accept generic statements of the form ‘Gs are f’ on relatively weak evidence, but that if we are unfamiliar with group G and we learn a generic statement about it, we still treat it inferentially in a much stronger way: all Gs are f. This paper makes use of notions like ‘representativeness’, ‘contingency’ and ‘relative difference’ from psychology to provide a uniform semantics of generics that explains why people accept generics based on weak evidence. (...) The spirit of the approach has much in common with Leslie’s cognition-based ideas about generics, but the semantics will be grounded on a strengthening of Cohen’s relative readings of generic sentences. In contrast to Leslie and Cohen, we propose a uniform semantic analysis of generics. The basic intuition is that a generic of the form ‘Gs are f’ is true because f is typical for G, which means that f is valuably associated with G. We will make use of Kahneman and Tversky’s Heuristics and Biases approach, according to which people tend to confuse questions about probability with questions about representativeness, to explain pragmatically why people treat many generic statements inferentially in a much stronger way. (shrink)

In terms of Groenendijk and Stokhofs (1984) formalization of exhaustive interpretation, many conversational implicatures can be accounted for. In this paper we justify and generalize this approach. Our justification proceeds by relating their account via Halpern and Moses (1984) non-monotonic theory of only knowing to the Gricean maxims of Quality and the first sub-maxim of Quantity. The approach of Groenendijk and Stokhof (1984) is generalized such that it can also account for implicatures that are triggered in subclauses not entailed by (...) the whole complex sentence. (shrink)

In this paper it will be shown how conditional presuppositions can be strengthened to unconditional ones if we assume that the antecedent and consequent of a conditional presupposition are independent of one another. Our notion of independence is very weak, and based on Lewis' notion of orthogonality of questions. It will be argued that our way of strengthening these presuppositions does not give rise to some wrong predictions Geurts argued other proposed strengthening accounts do.

A much discussed topic in the theory of choice is how a preference order among options can be derived from the assumption that the notion of ' choice' is primitive. Assuming a choice function that selects elements from each finite set of options, Arrow (Económica 26: 121-127,1959) already showed how we can generate a weak ordering by putting constraints on the behavior of such a function such that it reflects utility maximization. Arrow proposed that rational agents can be modeled by (...) such choice functions. Arrow's standard model of rationality has been criticized in economics and gave rise to approaches of bounded rationality. Two standard assumptions of rationality will be given up in this paper. First, the idea that agents are utility optimizers (Simon). Second, the idea that the relation of ' indifference' gives rise to an equivalence relation. To account for the latter, Luce (Econometrica 24: 178-191, 1956) introduced semi-orders. Extending some ideas of Van Benthem (Pac Philos Q 63: 193-203, 1982), we will show how to derive semi-orders (and so-called interval orders) based on the idea that agents are utility satisficers rather than utility optimizers. (shrink)

This study addresses the dynamical nature of a “representation‐hungry” cognitive task involving an imagined action. In our experiment, participants were handed rods that systematically increased or decreased in length on subsequent trials. Participants were asked to judge whether or not they thought they could reach for a distant object with the hand‐held rod. The results are in agreement with a dynamical model, extended from Tuller, Case, Ding, and Kelso (1994). The dynamical effects observed in this study suggest that predictive judgments (...) regarding the possibility or impossibility of a certain action can be understood in terms of dynamically evolving basins of attraction instead of as depending on representational structures. (shrink)

InSuppose and Tell, Williamson makes a new and original attempt to defend the material conditional account of indicative conditionals. His overarching argument is that this account offers the best explanation of the data concerning how people evaluate and use such conditionals. We argue that Williamson overlooks several important alternative explanations, some of which appear to explain the relevant data at least as well as, or even better than, the material conditional account does. Along the way, we also show that Williamson (...) errs at important junctures about what exactly the relevant data are. (shrink)

The appropriateness, or acceptability, of a conditional does not just ‘go with’ the corresponding conditional probability. A condition of dependence is required as well. In this paper a particular notion of dependence is proposed. It is shown that under both a forward causal and a backward evidential reading of the conditional, this appropriateness condition reduces to conditional probability under some natural circumstances. Because this is in particular the case for the so-called diagnostic reading of the conditional, this analysis might help (...) to explain some of Douven and Verbrugge’s empirical observations. (shrink)

In this paper, we explain why the antecedent of a biscuit conditional is relevant to its consequent by extending Douvenʼs evidential support theory of conditionals making use of utilities. By this extension, we can also explain why a biscuit conditional gives rise to the inference that the consequence is (most likely) true. Finally, we account for the intuition that (indicative) biscuit sentences are false when the antecedent is false and allow for counterfactual biscuits.

In this paper an approach to the exhaustive interpretation of answers is developed. It builds on a proposal brought forward by Groenendijk and Stokhof (1984). We will use the close connection between their approach and McCarthy's (1980, 1986) predicate circumscription and describe exhaustive interpretation as an instance of interpretation in minimal models, well-known from work on counterfactuals (see for instance Lewis (1973)). It is shown that by combining this approach with independent developments in semantics/pragmatics one can overcome certain limitations of (...) Groenenedijk and Stokhof's (1984) proposal. In the last part of the paper we will provide a Gricean motivation for exhaustive interpretation building on work of Schulz (to appear) and van Rooij and Schulz (2004). (shrink)

Objects have dispositions. Dispositions are normally analyzed by providing a meaning to disposition ascriptions like ‘This piece of salt is soluble’. Philosophers like Carnap, Goodman, Quine, Lewis and many others have proposed analyses of such disposition ascriptions. In this paper we will argue with Quine that the proper analysis of ascriptions of the form ‘x is disposed to m ’, where ‘x’ denotes an object, ‘m’ a manifestation, and ‘C’ a condition, goes like this: ‘x is of natural kind k’, (...) and the generic ‘ks are m ’ is true. For the analysis of the generic, we propose an analysis in terms of causal powers: ‘ks have the causal power to m’. The latter, in turn, is analyzed in a very precise way, making use of Pearl’s probabilistic graphical causal models. We will show how this natural kind-analysis improves on standard conditional analyses of dispositions by avoiding the standard counterexamples, and that it gives rise to precise observable criteria under which the disposition ascription is true. (shrink)

Many generic sentences express stable inductive generalizations. Stable inductive generalizations are typically true for a causal reason. In this paper we investigate to what extent this is also the case for the generalizations expressed by generic sentences. More in particular, we discuss the possibility that many generic sentences of the form ‘ks have feature e’ are true because kind k have the causal power to ‘produce’ feature e. We will argue that such an analysis is quite close to a probabilistic (...) based analysis of generic sentences according to which ‘relatively many’ ks have feature e, and that, in fact, this latter type of analysis can be ‘grounded’ in terms of causal powers. We will argue, moreover, that the causal power analysis is sometimes preferred to a correlation-based analysis, because it takes the causal structure that gives rise to the probabilistic data into account. (shrink)

We give derivations of two formal models of Gricean Quantity implicature and strong exhaustivity in bidirectional optimality theory and in a signalling games framework. We show that, under a unifying model based on signalling games, these interpretative strategies are game-theoretic equilibria when the speaker is known to be respectively minimally and maximally expert in the matter at hand. That is, in this framework the optimal strategy for communication depends on the degree of knowledge the speaker is known to have concerning (...) the question she is answering. In addition, and most importantly, we give a game-theoretic characterisation of the interpretation rule Grice (formalising Quantity implicature), showing that under natural conditions this interpretation rule occurs in the unique equilibrium play of the signalling game. (shrink)

In this paper, Universal any and Negative Polarity Item any are uniformly analyzed as ‘counterfactual’ donkey sentences (in disguise). Their difference in meaning is reduced here to the distinction between strong and weak readings of donkey sentences. It is shown that this explains the universal and existential character of Universal- and NPI-any, respectively, and the positive and negative contexts in which they are licensed. Our uniform analysis extends to the use of any in command and permission sentences. It predicts that (...) whereas the use of any in permission sentences is licensed and gives rise to a universal reading, it is not licensed in command sentences. (shrink)

Individuals make decisions under uncertainty every day. Decisions are based on in- complete information concerning the potential outcome or the predicted likelihood with which events occur. In addition, individuals’ choices often deviate from the rational or mathematically objective solution. Accordingly, the dynamics of human decision making are difficult to capture using conventional, linear mathematical models. Here, we present data from a 2-choice task with variable risk between sure loss and risky loss to illustrate how a simple nonlinear dynamical system can (...) be employed to capture the dynamics of human decision making under uncertainty (i.e., multistability, bifurcations). We test the feasibility of this model quantitatively and demonstrate how the model can account for up to 86% of the observed choice behavior. The implications of using dynamical models for explaining the nonlin- ear complexities of human decision making are discussed as well as the degree to which the theory of nonlinear dynamical systems might offer an alternative framework for understanding human decision making processes. (shrink)

In this article we discuss the notion of a linguistic universal, and possible sources of such invariant properties of natural languages. In the first part, we explore the conceptual issues that arise. In the second part of the paper, we focus on the explanatory potential of horizontal evolution. We particularly focus on two case studies, concerning Zipf's Law and universal properties of color terms, respectively. We show how computer simulations can be employed to study the large scale, emergent, consequences of (...) psychologically and psychologically motivated assumptions about the working of horizontal language transmission. (shrink)

This article aims to clarify and improve thinking on normative government laboratories: partly publically funded laboratories that work to improve the functioning of society, particularly through boosting innovation. This article focuses on a case study of TNO, a large Dutch laboratory, and an exemplary case of this type of laboratory. This article argues that TNO is perceived as a plug to fill a gap between knowledge production and use, in a belief that there is a direct and causal link between (...) laboratory knowledge production and use. As a plug to fill a gap, however, TNO, and laboratories like it, can never perform satisfactorily, making an enduring cycle of negative performance evaluations and major reorganizations inevitable. This article suggests that a network model of innovation might provide a way out of the impasse. (shrink)

ObjectiveFatigue after burns is often attributed to the hyperinflammatory and hypermetabolic response, while it may be best understood from a bio-psychological perspective, also involving the neuro-endocrine system. This longitudinal multi-center study examined the course of fatigue up to 18 months postburn. The contribution of bio-psychological factors, including burn severity, pain, and acute PTSD symptoms, to the course and persistence of fatigue was studied in a multifactorial model.MethodsParticipants were 247 adult burn survivors. Fatigue symptoms were assessed with the Multidimensional Fatigue Inventory (...) during the acute phase and subsequently at 3, 6, 12, and 18 months postburn, and were compared to population norms. Age, gender, burn severity, acute PTSD symptoms and pain were assessed as potential predictors of fatigue over time in a latent growth model.ResultsAt 18 months postburn, 46% of the burn survivors reported fatigue, including 18% with severe fatigue. In the acute phase, higher levels of fatigue were related to multiple surgeries, presence of pain, and higher levels of acute PTSD symptoms. Fatigue gradually decreased over time with minor individual differences in rate of decrease. At 18 months, pain and acute PTSD symptoms remained significant predictors of fatigue levels.ConclusionsProtracted fatigue after burns was found in almost one out of five burn survivors and was associated with both pain and acute PTSD symptoms. Early detection of PTSD symptoms and early psychological interventions aimed at reducing PTSD symptoms and pain may be warranted to reduce later fatigue symptoms. (shrink)

The principle of stability now says that if sentence ϕ is true/false in a model M, then ϕ has to stay true/false if M is getting more precise. Formally, let M = D, I be a refinement of M = D, I . Then it has to be the case that for all ϕ: (i) If VM(ϕ) = 1, then VM (ϕ) = 1. (ii) If VM(ϕ) = 0, then VM (ϕ) = 0.

Individuals make decisions under uncertainty every day based on incomplete information concerning the potential outcome of the choice or chance levels. The choices individuals make often deviate from the rational or mathematically objective solution. Accordingly, the dynamics of human decision-making are difficult to capture using conventional, linear mathematical models. Here, we present data from a two-choice task with variable risk between sure loss and risky loss to illustrate how a simple nonlinear dynamical system can be employed to capture the dynamics (...) of human decision-making under uncertainty (i.e., multi-stability, bifurcations). We test the feasibility of this model quantitatively and demonstrate how the model can account for up to 86% of the observed choice behavior. The implications of using dynamical models for explaining the nonlinear complexities of human decision-making are discussed, as well as the degree to which nonlinear dynamical systems theory might offer an alternative framework for understanding human decision-making processes. (shrink)